626D - Jerry's Protest - CodeForces Solution

#include <bits/stdc++.h>

#define f first
#define s second
#define loop(i, n) for (int i = 0; i < n; ++i)
#define read(a, n) loop($, n) scanf("%d", &a[$]);
#define show(a, n)                  \
    loop($, n) cout << a[$] << " "; \
    cout << endl;

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// SET WITH INDEXING
// Implements logarithmic find_by_order() and order_of_key()
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

/*  // RANDOM NUMBER GENERATOR
// rng() generates u.a.r. from [0, 2^32 - 1]
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
*/

const int N = 2000;

int a[N], d[N * N];

int main(){
    /*
    auto start = chrono::high_resolution_clock::now();
    */
    
    ios_base::sync_with_stdio(false);   // unsync C- and C++-streams (stdio, iostream)
    cin.tie(NULL);  // untie cin from cout (no automatic flush before read)

    int n; scanf("%d", &n);
    read(a, n);
    sort(a, a + n);
    unordered_map<int, int> cnt;
    int den = 0;
    loop(i, n){
        for(int j = i + 1; j < n; ++j){
            cnt[a[j] - a[i]]++;
            d[den++] = a[j] - a[i];
        }
    }
    sort(d, d + den);
    ull num = 0;
    for(auto it1 = cnt.begin(); it1 != cnt.end(); ++it1){
        for(auto it2 = cnt.begin(); it2 != cnt.end(); ++it2){
            ull w = it1->s * it2->s;
            num += w * (den - (lower_bound(d, d + den, it1->f + it2->f + 1) - d));
        }
    }
    printf("%.10f\n", (double) num / den / den / den);

    /*
    auto stop = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    cout << duration.count() << endl;
    */
    return 0;
}